package 剑指offer;

public class p42连续子数组的最大和 {
    public int maxSubArray(int[] nums) {
        //滴滴面试
        //动态规划
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        for (int i = 1; i <nums.length; i++) {
            if (dp[i-1]>0) {
                dp[i]=dp[i-1]+nums[i];
            }else {
                dp[i]=nums[i];
            }
        }

        int max=Integer.MIN_VALUE;
        for (int i = 0; i <dp.length; i++) {
            if (dp[i]>max) {
                max=dp[i];
            }
        }
        return max;
    }


    public int maxSubArray1(int[] nums) {
        if (nums.length==0) {
            return -1;
        }

        int[] findArr=new int[nums.length];
        findArr[0]=nums[0];
        int maxNum=findArr[0];

        for (int i = 1; i <nums.length; i++) {
            if (findArr[i-1] >= 0) {
                //findArr[i-1]为正数，就将nums[i]+findArr[i-1] 存入 findArr[i]中
                findArr[i]=findArr[i-1]+nums[i];
            }else {
                //findArr[i-1]为负数，则将nums[i] 直接存入 findArr[i]中
                findArr[i]=nums[i];
            }

            if (maxNum<findArr[i]) {
                maxNum=findArr[i];
            }
        }

        return maxNum;
    }



}
